A network processor is a programmable device that is optimized for processing packets at high speed. As the processing time available for processing received packets decreases in proportion to the increase in the rate at which packets are transmitted over a network, a network processor may include a plurality of programmable packet-processing engines to process packets in parallel. The packet-processing engines run in parallel, with each packet processing engine (micro engine) handling packets for a different flow (or connection) which may be processed independently from each other.
Some of the packet processing engines may be used to perform a scheduling function that determines the order in which packets are de-queued after they have been processed. A scheduler may be hierarchical, that is, may implement more than one level of scheduling schemes. For example, a hierarchical scheduler may implement three-level inline scheduling with three different schemes at the 3 levels i.e. by implementing weighted round-robin (WRR) scheduling on ports, strict priority scheduling among groups of queues per port, and Deficit Round Robin (DRR) scheduling among queues within a queue group. The queue, queue group and ports that constitute the three levels of the hierarchy are typically referred to as nodes.
Typically, a scheduler uses packet departure time as selection criterion for de-queuing packets. This involves finding the packet that has the earliest departure time by first sorting the departure times of queued packets in either ascending or descending order. However, as the number of bits allocated for storing a packet's departure time is limited, departure times wrap around when they cross over the number of allocated bits. To check for departure time wrap occurrence, a scheduler typically explicitly checks each departure time.
In addition to checking for departure time wrap occurrence, a scheduler may also exclude nodes that are rate limited (use a token based scheduling scheme) from the sort calculation and may schedule priority packets ahead of other non priority packets. Checking for departure time wrap around, rate limited nodes and priority packets requires additional compute cycles, for example, additional compute cycles to perform check-and-branch instructions. These additional instructions reduce available compute bandwidth for scheduling packets.
Furthermore, in a hierarchical scheduler a selection process is performed at each level of the hierarchy. Determining a packet to advance through the hierarchy needs to be performed very efficiently, as multiple selections are required for scheduling each packet.
Although the following Detailed Description will proceed with reference being made to illustrative embodiments of the claimed subject matter, many alternatives, modifications, and variations thereof will be apparent to those skilled in the art. Accordingly, it is intended that the claimed subject matter be viewed broadly, and be defined only as set forth in the accompanying claims.